/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

 //用栈，记录先序遍历时每个节点的右节点
// class Solution {
// public:
//     stack<TreeNode*> st;
//     void flatten(TreeNode* root) {
//         if (root == nullptr)
//             return;

//         st.push(root->right);
//         TreeNode* cur = root, *pos = root->left;

//         while (true)
//         {
//             while (pos)
//             {
//                 cur->right = pos;
//                 cur->left = nullptr;
//                 if (pos->right)
//                 {
//                     st.push(pos->right);
//                     pos->right = nullptr;
//                 }
//                 pos = pos->left;
//                 cur = cur->right;
//             }
//             if (st.empty())
//                 break;

//             TreeNode* node = st.top();
//             st.pop();
//             pos = node;
//         }
//     }
// };

//递归，反前序遍历
//右子树 -> 左子树 -> 根
// class Solution {
// public:
//     TreeNode* prevNode = nullptr;
//     void flatten(TreeNode* root) {
//         if (root == nullptr)
//             return;

//         flatten(root->right);
//         flatten(root->left);
//         root->right = prevNode;
//         root->left = nullptr;
//         prevNode = root;
//     }
// };


//空间O(1)
//和反前序遍历的思想类似，不断将左边的节点放到右边，同时将右边的节点放到左边节点的后面
class Solution {
public:
    void flatten(TreeNode* root) {
        if (root == nullptr)
            return;

        TreeNode* cur = root;

        while (cur)
        {
            TreeNode* LRNode = cur->left, *next = cur->left;
            if (LRNode)
            {
                while (LRNode->right)   //找到cur左边节点的右子树的最右节点
                    LRNode = LRNode->right;
                LRNode->right = cur->right;
                cur->right = next;
                cur->left = nullptr;
            }
            cur = cur->right;
        }
    }
};
